/*
 * @lc app=leetcode.cn id=32 lang=cpp
 *
 * [32] 最长有效括号
 */

#include <limits.h>

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;

// @lc code=start
class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> charSet;         // 记录当前未匹配的符号的下标
        int maxLength = 0;          // 记录有效字串的最大长度
        
        charSet.push(-1);

        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                charSet.push(i);
            } else {
                if (charSet.top() != -1 && s[charSet.top()] == '(') {
                    // 如果可以匹配，栈顶元素出栈
                    charSet.pop();
                } else {
                    // 如果不能匹配，将当前元素入栈
                    charSet.push(i);
                }
            }

            maxLength = max(maxLength, i - charSet.top());
        }
        
        return maxLength;
    }
};
// @lc code=end

